package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.ListNode;

public class LC148_SortList {
    public static void main(String[] args) {

    }

    /**
     * 归并排序
     */
    static class Solution {
        public ListNode sortList(ListNode head) {
            if(head == null || head.next == null) {
                return head;
            }

            ListNode head1 = head;
            ListNode head2 = split(head);

            head1 = sortList(head1);
            head2 = sortList(head2);

            return merge(head1, head2);
        }

        private ListNode split(ListNode head) {
            ListNode slow = head, fast = head.next;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            ListNode secondPart = slow.next;
            slow.next = null;
            return secondPart;
        }

        private ListNode merge(ListNode head1, ListNode head2) {
            ListNode dummy = new ListNode(0), current = dummy;
            while (head1 != null && head2 != null) {
                if(head1.val < head2.val) {
                    current.next = head1;
                    head1 = head1.next;
                } else {
                    current.next = head2;
                    head2 = head2.next;
                }
                current = current.next;
            }
            current.next = (head1 == null ? head2 : head1);
            return dummy.next;
        }
    }
}